package math;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @author pengfei.hpf
 * @date 2020/3/20
 * @verdion 1.0.0
 * 给定一个32位正整数 n，你需要找到最小的32位整数，其与 n 中存在的位数完全相同，并且其值大于n。如果不存在这样的32位整数，则返回-1。
 *
 * 示例 1:
 *
 * 输入: 12
 * 输出: 21
 * 示例 2:
 *
 * 输入: 21
 * 输出: -1
 */
public class NextGreaterElement {
    public int nextGreaterElement(int n) {
        if(n < 10){
            return -1;
        }
        List<Integer> list = changeToList(n);
        int index = list.size() - 2;
        while(index >= 0){
            if(list.get(index) < list.get(index + 1)){
                break;
            }
            index --;
        }
        if(index < 0){
            return -1;
        }
        return resort(index, list);
    }

    private List<Integer> changeToList(int n){
        List<Integer> list = new ArrayList<>();
        while(n > 0){
            int i = n % 10;
            list.add(0, i);
            n /= 10;
        }
        return list;
    }

    private long changeToNum(List<Integer> list, int end){
        long num = 0;
        for(int i = 0; i <= end; i ++){
            num = num * 10 + list.get(i);
        }
        return num;
    }

    private int resort(int start, List<Integer> list){
        int min = list.get(start + 1);
        int index = start + 1;
        List<Integer> newlist = new ArrayList<>();

        for(int i = index + 1; i < list.size(); i ++){
            if(list.get(i) < min && list.get(i) > list.get(start)){
                min = list.get(i);
                index = i;
            }
        }
        list.set(index, list.get(start));
        list.set(start, min);
        for(int i = start + 1; i < list.size(); i ++){
            newlist.add(list.get(i));
        }
        Collections.sort(newlist);
        long num = changeToNum(list, start);
        long num2 = changeToNum(newlist, newlist.size() -1);
        num = num * (long)Math.pow(10, newlist.size()) +  num2;
        return num> Integer.MAX_VALUE?  -1: (int) num;

    }
}
